package offer.offer04;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 95, 56, 看起来这种在一定情况下重新扫描O(k), 平时O(1)的算法效果还可以。
 */
public class Solution59 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        int[] maxLoc = new int[2];//放一下上一个最大值的位置和大小{位置, 大小}
        maxLoc[0] = 0;
        maxLoc[1] = nums[0];
        int[] maxResult = new int[nums.length - k + 1];
        //先找到第一个窗口的最大值
        for(int i = 1; i < k; i++){
            if(nums[i] > maxLoc[1]){
                maxLoc[1] = nums[i];
                maxLoc[0] = i;
            }
        }
        maxResult[0] = maxLoc[1];

        for(int i = k; i < nums.length; i++){
            if(maxLoc[0] != i - k){
                if(nums[i] > maxLoc[1]){
                    maxLoc[0] = i; maxLoc[1] = nums[i];
                }else {
                }
            }else {
                //上一个最大值到了滑动窗口之外, 我们重新扫描窗口内的值
                maxLoc[0] = i - k + 1;
                maxLoc[1] = nums[i - k + 1];
                for(int j = i - k + 2; j <= i; j ++ ){
                    if(nums[j] > maxLoc[1]){
                        maxLoc[1] = nums[j];
                        maxLoc[0] = j;
                    }
                }
            }
            maxResult[i - k + 1] = maxLoc[1];
        }
        return maxResult;
    }

    /**
     * deque.peekLast(), 返回最后的, 但是不删除;
     * deque是一个递减序列, 包含着前k个值中的递减序列(不是排序, 是一个个扫, 两个大值之间的小值会被删除, 4 1 3, 会删除1,
     * 之后每次扫到一个值, 从后往前把小于他的删除掉, 再把他放进去
     * 如果窗口移动时把最大值remove了, 那就找第二个值, 都是int, 用值的大小来判断就行了;
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int i = 0; i < k; i++) { // 未形成窗口
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        for(int i = k; i < nums.length; i++) { // 形成窗口后
            if(deque.peekFirst() == nums[i - k])
                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }

    public static void main(String[] args) {
        int[] input = new int[]{1,3,-1,-3,5,3,6,7};
        System.out.println(Arrays.toString(new Solution59().maxSlidingWindow(input, 3)));
    }
}
